/*
 * @lc app=leetcode.cn id=47 lang=cpp
 *
 * [47] 全排列 II
 */

// @lc code=start
class Solution
{
public:
  int n;
  set<vector<int>> v_set;

  vector<vector<int>> permuteUnique(vector<int>& nums)
  {
    this-> n = nums.size();
    this->v_set = set<vector<int>>();
    vector<bool> used(n, false);
    vector<int> tmp;
    DFS(nums, 0, used, tmp);
    return vector<vector<int>>(v_set.begin(), v_set.end());
  }

  void DFS(vector<int>& nums, int deep, vector<bool>& used, vector<int>& tmp)
  {
    if (deep == n)
      v_set.insert(tmp);
    else {
      for (int i = 0; i < n; ++i) {
        if (!used[i]) {
          used[i] = true;
          tmp.push_back(nums[i]);
          DFS(nums, deep + 1, used, tmp);
          tmp.pop_back();
          used[i] = false;
        }
      }
    }
  }
};
// @lc code=end
